//
//  72_编辑距离.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/11.
/**
 https://leetcode.cn/problems/edit-distance/description/
 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。

 你可以对一个单词进行如下三种操作：

 插入一个字符
 删除一个字符
 替换一个字符
  
 示例 1：

 输入：word1 = "horse", word2 = "ros"
 输出：3
 解释：
 horse -> rorse (将 'h' 替换为 'r')
 rorse -> rose (删除 'r')
 rose -> ros (删除 'e')
 示例 2：

 输入：word1 = "intention", word2 = "execution"
 输出：5
 解释：
 intention -> inention (删除 't')
 inention -> enention (将 'i' 替换为 'e')
 enention -> exention (将 'n' 替换为 'x')
 exention -> exection (将 'n' 替换为 'c')
 exection -> execution (插入 'u')
 */

import UIKit

class GetMinDistance: NSObject {
    func QA() {
        print(minDistance("horse", "ros"))
        print(minDistance("intention", "execution"))

    }
    func minDistance(_ word1: String, _ word2: String) -> Int {
        let array1 = Array(word1)
        let array2 = Array(word2)
        let count1 = word1.count
        let count2 = word2.count
        let temp = Array(repeating: 0, count: count2 + 1)
        var dp = Array(repeating: temp, count: count1 + 1)
        for j in 0...count1 {
            dp[j][0] = j
        }
        for i in 0...count2 {
            dp[0][i] = i
        }
        
        var i = 1
        while i <= count1 {
            var j = 1
            while j <= count2 {
                let left = dp[i][j - 1] + 1 // 添加
                let top = dp[i - 1][j] + 1 //  删除
                let min1 = min(left, top)
                var leftTop = dp[i - 1][j-1] // 替换
                if array1[i - 1] != array2[j - 1] {
                    leftTop += 1
                }
                dp[i][j] = min(min1, leftTop)
                j += 1
            }
            i += 1
        }
        return dp[count1][count2]
    }
}
